import java.util.*;

/*
题目：前K个高频单词
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
 */
class TopKFrequent {
    public List<String> topKFrequent(String[] words, int k) {
        //1. 先统计单词出现的次数
        Map<String, Integer> map = new HashMap<> ();
        for (String x : words) {
            if (map.containsKey(x)) {
                int val = map.get(x);
                map.put(x, val + 1);
            } else {
                map.put(x, 1);
            }
        }

        //2. 构造小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<> (new TimeComparator());
        //现在需要遍历map集合，所以要先把map集合中的Key - Value键值对都存储在Set中，进行遍历
        Set<Map.Entry<String, Integer>> set = map.entrySet();

        for (Map.Entry<String, Integer> entry : set) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {  //找到了更高频率的
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if (top.getValue().compareTo(entry.getValue()) == 0 && top.getKey().compareTo(entry.getKey()) > 0) { //相同频率，但是堆顶字典序大
                    minHeap.poll();
                    minHeap.offer(entry);
                }
            }
        }

        List<String> list = new ArrayList<> ();
        for (int i = 0; i < k; i++) {
            list.add(minHeap.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}

class TimeComparator implements Comparator<Map.Entry<String, Integer>> {

    public int compare (Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
        if (o1.getValue().compareTo(o2.getValue()) == 0) {  //如果频率相同，那就需要字典序小的排前面（后面有反转）
            return o2.getKey().compareTo(o1.getKey());
        }
        return o1.getValue().compareTo(o2.getValue());
    }
}